Congruencia modulo n
En Z:aRb⇔a≡b(n)⇔n∣a−b
x={y∈Z/y=nk+xcon k∈Z}
Zn={0,1,2,…,n−1}
∀x,y∈Z:Si x∈a(n)∧y∈b(n)⇒x+y∈a+b(n)
∀x,y∈Z:Si x∈a(n)∧y∈b(n)⇒x⋅y∈a⋅b(n)
Funcion de Euler
ϕ(n)=∣{x∈N/x≤n∧mcd(x,n)=1}∣
Osea me devuelve cuantos numeros coprimos hay hasta el numero n
- Si p es un numero primo, entonces: ϕ(p)=p−1
- Si n es un numero natural y p es numero primo:
ϕ(pn)=pn⋅(1−p1)ϕ(pn)=pn−1(p−1)
- Si n,m∈N y mcd(n,m)=1:ϕ(n⋅m)=ϕ(n)⋅ϕ(m)
-
ϕ(n)=n⋅(1−p11)⋅(1−p21)⋅⋯⋅⋅(1−pr1)
Teorema de Fermat
Se usa para las ecuaciones de congruencia o para calcular las divisiones de numeros demasiado grandes
Si p es primo∧mcd(a,p)=1⇒ap−1≡1(p)
Este teorema se usa para ir simplificando los exponentes para verificar si el resto de una division cae en una clase
Teorema de Euler-Fermat
Si mcd (a,n)=1⇒aϕ(n)≡1(n)
Ecuaciones Lineales de Congruencia
a⋅x≡b(n)
Sea a⋅x≡b(n).Si mcd (a,n)=1 entonces hay solucion.
x=aϕ(n)−1⋅b
a⋅x≡b(n) tiene solucion ⇔mcd(a,n)∣b y la cantidad de soluciones es mcd(a,n)
Esto sirve tambien para simplificar las ecuaciones, se puede dividir termino a termino por la cantidad de soluciones, luego resolver la ecuacion, y finalmente al resultado de la eq simplificada se le suma el modulo simplificado la cantidad de soluciones que hallamos obtenido.
Si:a⋅c≡b⋅c(n)∧mcd(c,n)=1Entonces a≡b(n)